import java.util.Arrays;

public class project {
    public String removeOccurrences(String s, String part) {
        while (s.contains(part)){
            int index=s.indexOf(part);
            s=s.substring(0,index)+s.substring(index+part.length());
        }
        return s;
    }
















    public int minFallingPathSum(int[][] matrix) {
        int len=matrix.length;
        for(int i=1;i<len;i++){
            for(int j=0;j<len;j++){
                int min=0;
                if(j==0){
                    min=Math.min(matrix[i-1][j+1],matrix[i-1][j]);
                }else if(j==len-1){
                    min=Math.min(matrix[i-1][j-1],matrix[i-1][j]);
                }else{
                    min=Math.min(matrix[i-1][j],Math.min(matrix[i-1][j-1],matrix[i-1][j+1]));
                }
                matrix[i][j]+=min;
            }
        }
        Arrays.sort(matrix[len-1]);
        return matrix[len-1][0];
    }

















    public boolean checkPowersOfThree(int n) {
        while (n>0){
            if(n%3==2){
                return false;
            }
            n/=3;
        }
        return true;
    }














    public int change(int amount, int[] coins) {
        int[] dp=new int[amount+1];
        dp[0]=1;
        for(int coin:coins){
            for(int i=coin;i<=amount;i++){
                dp[i]+=dp[i-coin];
            }
        }
        return dp[amount];
    }
















    public int[] arr;
    public int bestRotation(int[] nums) {
        arr=new int[nums.length];
        Arrays.fill(arr,0);
        for(int i=0;i<nums.length;i++){
            if(nums[i]<=i){
                arr[0]++;
                arr[i-nums[i]+1]--;
                arr[i+1]++;
            }else{
                arr[i+1]++;
                arr[i+1+nums.length-nums[i]]--;
            }
        }
        int max=0;
        int k=0;
        int cur=0;
        for(int i=0;i<nums.length;i++){
            cur+=arr[i];
            if(cur>max){
                cur=max;
                k=i;
            }
        }
        return k;
    }
}
